package example5;

//494. 目标和
public class LeetCode494 {
    public static void main(String[] args) {
        int[] arr = {1,1,1,1,1};
        int[] arr2 = {1,0};
        int[] arr3 = {7,9,3,8,0,2,4,8,3,9};
        int[] arr4 = {9,7,0,3,9,8,6,5,7,6};
        int[] arr5 = {2,107,109,113,127,131,137,3,2,3,5,7,11,13,17,19,23,29,47,53};
        System.out.println(new Solution494_3().findTargetSumWays(arr5,1000));
    }
}

/**
 * 方法三：方法二的优化   优化了空间复杂度为一维数组
 * 因为对于方法二来说计算dp[i]这一行时，只跟dp[i-1]有关，而且计算dp[i][j]时海之会用到j前面的已经计算好的方案，
 * 而不会用到j后面的方案，所以在j的循环中，可以从大到小遍历j，这样就可以用一维数组dp[]存储最终的结果，循环结束后，
 * dp存储的就是前n个数，从0到neg所有和的所有方案数，最终返回dp[neg]即可。
 */
class Solution494_3 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        int n = nums.length;
        int count0 = 0;
        for(int i=0;i<n;i++){
            sum += nums[i];
            if(nums[i] == 0)    count0++;
        }
        if((sum % 2 == 1 && target % 2 == 0) || (sum % 2 == 0 && target % 2 == 1)){
            //奇数减偶数不可能为偶数，偶数减偶数也不可能为奇数
            return 0;
        }
        if(sum < target)    return 0;
        if(sum == target)   return (int)Math.pow(2,count0);
        int neg = (sum - target) / 2;
        int[] dp = new int[neg+1];
        for(int i=0;i<n;i++){
            for(int j=neg;j>=0;j--){
                if(i == 0){
                    if(nums[0] == j){
                        dp[j] = 1;
                    }
                }else{
                    if(nums[i] < j){
                        dp[j] = dp[j] + dp[j-nums[i]];
                    }else if(nums[i] == j){
                        dp[j] = dp[j] + dp[j-nums[i]] + 1;
                    }
                }
            }
        }
        return dp[neg];
    }
}

/**
 * 方法二：动态规划
 * 首先先计算数组中所有数的和sum，因为目标target，假设带减号的数的和为neg，那么带加号的数的和就是sum-neg。
 * 那么 sum - neg - neg = target。所以 sum - 2neg = target， neg = (sum - target) / 2。
 * 但是要注意，代码中的/除号都是整除，所以，当sum 为奇数，但target为偶数时，此时不存在正确的neg，
 * 因为neg为整数，2neg为偶数，奇数 - 偶数 != 偶数。所以这种情况直接是边界情况。同理sum为偶数，target为奇数时也是如此。
 *
 * 那么既然知道了neg，要找最终的方案数，那么本题就可以直接转换成：从数组中挑选几个数，使这几个数的和为neg，求出这些数的组合有多少种。
 *
 * 那么就可以采用动态规划，dp[n][neg+1]，dp[i][j]表示下标i及i之前的所有数中，能够组成和为j的所有数的组合。
 * 最终dp[n-1][neg]就是本题答案。
 */
class Solution494_2 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        int n = nums.length;
        int count0 = 0;
        for(int i=0;i<n;i++){
            sum += nums[i];
            if(nums[i] == 0)    count0++;
        }
        if((sum % 2 == 1 && target % 2 == 0) || (sum % 2 == 0 && target % 2 == 1)){
            //奇数减偶数不可能为偶数，偶数减偶数也不可能为奇数
            return 0;
        }
        if(sum < target)    return 0;
        if(sum == target)   return (int)Math.pow(2,count0);
        int neg = (sum - target) / 2;
        int[][] dp = new int[n][neg+1];
        for(int i=0;i<n;i++){
            for(int j=0;j<=neg;j++){
                if(i == 0){
                    if(nums[0] == j){
                        dp[0][j] = 1;
                    }
                }else{
                    if(nums[i] > j){
                        dp[i][j] = dp[i-1][j];
                    }else if(nums[i] == j){
                        dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]] + 1;
                    }else{
                        dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];
                    }
                }
            }
        }
        return dp[n-1][neg];
    }
}

/**
 * 方法一：回溯，枚举出所有的表达式情况。时间复杂度 O(2的n次方)，空间复杂度 O(n)
 */
class Solution494_1 {
    private int count;

    public int findTargetSumWays(int[] nums, int target) {
        fun(nums,0,0,target);
        return count;
    }

    public void fun(int[] nums,int index,int nowSum,int target){
        if(index == nums.length){
            if(nowSum == target){
                count++;
            }
            return;
        }
        fun(nums,index+1,nowSum+nums[index],target);
        fun(nums,index+1,nowSum-nums[index],target);
    }
}
